public class day230315 {
    // 二维数组中的查找
    public boolean Find(int target, int [][] array) {
        int i = 0;
        int j = array[0].length - 1;
        // 从右上角开始遍历
        // 右上角这个值, 在这一行里时最大的, 在这一列里是最小的
        while (i < array.length && j >=0) {
            if (array[i][j] < target) {
                // 小于目标值, 排除这一行
                i++;
            } else if (array[i][j] > target) {
                // 大于目标值, 排除这一列
                j--;
            } else {
                return true;
            }
        }
        return false;
    }


    // 旋转数组的最小数字
    public int minNumberInRotateArray(int [] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int mid = 0;

        while (array[left] >= array[right]) {
            if (left == right - 1) {
                // left 和 right 相邻
                // 查找结束
                // 返回较小的right
                mid = right;
                break;
            }
            mid = (left + right) >> 1;
            if (array[left] == array[right] && array[mid] == array[right]) {
                // 如果left  mid  right  都相等
                // 用基础的遍历来找
                for (int i = 0; i < array.length - 1; i++) {
                    if (array[i] > array[i + 1]) {
                        return array[i+1];
                    }
                }
            }
            if (array[mid] >= array[left]) {
                // mid 大于 left
                // 说明 mid 在前半部分
                left = mid;
            } else {
                // 说明 mid 在后半部分
                right = mid;
            }
        }
        return array[mid];
    }
}
